package org.basis.algorithm.practice;

import lombok.Data;

/**
 * 检查是否是平衡二叉树
 *
 * @author Mr_wenpan@163.com 2022/03/22 11:54
 */
public class IsBalancedBinaryTree {

    public static void main(String[] args) {

    }

    /**
     * 检查一棵二叉树是否为平衡二叉树
     */
    public static boolean checkBalancedBinaryTree(TreeNode head) {
        if (head == null) {
            return true;
        }
        return check(head).isBalance;
    }

    /**
     * 平衡二叉树定义：它是一棵【空树】或它的左右两个子树的【高度差的绝对值不超过1】，并且【左右两个子树都是一棵平衡二叉树】
     * 如果整棵树是平衡二叉树，那么该树上任意一棵子树都是平衡二叉树
     */
    public static CheckResult check(TreeNode node) {
        // base case
        if (node == null) {
            // 空节点一定是平衡树，并且树高为0
            return new CheckResult(true, 0);
        }
        // 递归检查他的左右子树（问左右孩子要信息）
        CheckResult leftResult = check(node.left);
        CheckResult rightResult = check(node.right);
        // 汇总左右子树的结果
        int high = Math.max(leftResult.high, rightResult.high) + 1;
        // 需要满足左树是平衡树并且右树也是平衡树并且左右树的高度差不能超过1
        boolean isBalance = leftResult.isBalance && rightResult.isBalance && Math.abs(leftResult.high - rightResult.high) <= 1;
        return new CheckResult(isBalance, high);
    }

    /**
     * 自定义的返回结果
     */
    @Data
    static class CheckResult {
        /**
         * 是否是平衡树
         */
        boolean isBalance;
        /**
         * 树的高度
         */
        int high;

        public CheckResult(boolean isBalance, int high) {
            this.isBalance = isBalance;
            this.high = high;
        }
    }

    @Data
    static class TreeNode {
        String val;
        TreeNode left;
        TreeNode right;
    }
}

